package 蓝桥杯算法;

import java.util.*;

public class day30 {
    public void main(String[] args) {
       List<List<Integer>> result=new ArrayList<>();
       List<Integer> path=new ArrayList<>();
       int max=Integer.MAX_VALUE;
       //深度搜索
       int m=4;
       int n=5;
       int[][]graph={{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}};
       Boolean[][]visited=new Boolean[m][n];
       int res=0;
       for(int i=0;i<m;i++) {
           for (int j = 0; j < n; j++) {
               if (!visited[i][j] && graph[i][j] == 1) {
                   res++;
                   visited[i][j] = true;
                   //对其周围进行深搜
                   dfs1(visited, i, j, graph);
               }
           }
       }
       //广度搜索
        Boolean[][]visited1=new Boolean[m][n];
      int ans=0;
       for(int i=0;i<m;i++){
           for(int j=0;j<n;j++){
               if(!visited[i][j]&&graph[i][j]==1){
                   bfs(graph,visited1,i,j);
                   ans++;
               }
           }
       }
       //岛屿的最大面积
        Boolean[][] visited2=new Boolean[m][n];
       int maxsum=0;
       int count=0;
       for(int i=0;i<m;i++){
           for(int j=0;j<n;j++){
               if(!visited2[i][j]&&graph[i][j]==1){//说明存在岛屿
                  count=0;
                  dfs3(graph,visited2,i,j,count);//每次操作后会生成一个值
                  maxsum=Math.max(maxsum,count);


               }
           }
       }
    }
    public void dfs3(int[][]graph,Boolean[][]visited,int x,int y,int count){//深度搜索
        //每次进行深搜，说明该结点符合相关的条件
        count++;
        int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};
int min=Integer.MIN_VALUE;
        visited[x][y]=true;
        for (int i = 0; i < 4; i++) {
            int nextX=x+dir[i][0];
            int nextY=y+dir[i][1];
            //水或者已经访问过的跳过
            if(nextX<0||nextY<0
                    ||nextX>=graph.length||nextY>=graph[0].length
                    ||visited[nextX][nextY]||graph[nextX][nextY]==0)
                continue;

            dfs3(graph,visited,nextX,nextY,count);
        }



    }
    public void bfs(int[][]graph,Boolean[][]visited,int x,int y){
        int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};

        Queue<Pair<Integer,Integer>> queue=new LinkedList<>();
        queue.add(new Pair(x,y));
        visited[x][y]=true;

        while(!queue.isEmpty()){
            //直到该队列结束
            int curx=queue.poll().getFirst();
            int cury=queue.peek().getSecond();
            for(int i=0;i<4;i++) {
                int nextx = x + dir[i][0];
                int nexty = y + dir[i][1];
                if (nextx < 0 || nextx>= graph.length || nexty < 0 || nexty>= graph[0].length) {
                    continue;
                }//去除越界部分
                if(!visited[nextx][nexty]&&graph[nextx][nexty]==1){
                    queue.add(new Pair(nextx,nexty));
                    visited[nextx][nexty]=true;
                }
            }

        }
    }

    public class Pair<F,S>{//用于让队列形成两个值
        private F first;
        private S second;
        private Pair(F first,S second){
            this.first=first;
            this.second=second;
        }

        public F getFirst() {
            return first;
        }

        public S getSecond() {
            return second;
        }
    }
    public static void dfs1(Boolean[][] visited, int x, int y, int[][] graph){//深受
     int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};
     for(int i=0;i<4;i++){
         int nextx=x+dir[i][0];
         int nexty=y+dir[i][1];
         if(nexty<0||nextx<0||nextx>=graph.length||nexty>=graph[0].length){
             //x和y的相关坐标限制不同
             continue;
         }
         if(!visited[nextx][nexty]&&graph[nextx][nexty]==1){
             visited[nextx][nexty]=true;
             dfs1(visited,nextx,nexty,graph);
             //继续王琦旁边深搜，看看是否有新的连接
         }
     }
    }
    //邻接矩阵
    public void dfs(int[][] graph,int x,int y, List<List<Integer>> result, List<Integer> path){
        if(x==y){
          result.add(new ArrayList<>(path));
          return;
        }
        for(int i=0;i<graph.length;i++){
            if(graph[x][i]==1){
                path.add(i);
                dfs(graph,i,y,result,path);
                //继续向下进行递归
                path.remove(path.size()-1);
            }
        }
    }




}
